package com.h2cloud.tree;

import java.util.Arrays;

/**
 * @author: wulongkai
 * @create: 2023-03-22 11:15
 **/
class NumArray {
    int[] tree;
    int[] nums;
    int n;

    int lowbit(int x) {
        return x & -x;
    }

    public NumArray(int[] _nums) {
        nums = _nums;
        n = nums.length;
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            add(i + 1, nums[i]);
        }
    }

    void add(int index, int detal) {
        while (index <= n) {
            tree[index] += detal;
            index += lowbit(index);
        }
    }

    int query(int index) {
        int ans = 0;
        while (index > 0) {
            ans += tree[index];
            index -= lowbit(index);
        }
        return ans;
    }

    public void update(int index, int val) {
        add(index + 1, val - nums[index]);
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5};
        NumArray numArray = new NumArray(arr);
        System.out.println("Arrays.toString(numArray.nums) = " + Arrays.toString(numArray.nums));
        System.out.println("Arrays.toString(numArray.tree) = " + Arrays.toString(numArray.tree));
        int query = numArray.sumRange(0, 1);
        System.out.println("query = " + query);

        numArray.update(1, 2);
        System.out.println("Arrays.toString(numArray.nums) = " + Arrays.toString(numArray.nums));
        System.out.println("Arrays.toString(numArray.tree) = " + Arrays.toString(numArray.tree));
        query = numArray.sumRange(1, 2);
        System.out.println("query = " + query);
    }
}
